
#include "grafo.h"

void tratarLinea(string line, string& first,string& second,string& thirth,string& fourth,string& fiveth,int cant){
                vector<string> entradaSplit;
                int fromIndex = 0;
                int length = 0;
                for(int i=0; i<line.length(); i++) {
                        if(i == line.length() - 1) {
                                length++;
                                entradaSplit.push_back(line.substr(fromIndex, length));
                        } else if(line[i] == ' ') {
                                entradaSplit.push_back(line.substr(fromIndex, length));
                                fromIndex = i+1;
                                length = 0;
                        } else {
                                length++;
                        }
                }
                first = entradaSplit[0].c_str();
                second = entradaSplit[1].c_str();
				thirth = entradaSplit[2].c_str();
				fourth = entradaSplit[3].c_str();
				if(cant == 5) fiveth  = entradaSplit[4].c_str();

}
void resolver(vector<Edge> aristas,int nodesCant,int edgesCount,int origen,int destino,int K){

	//Estandarizando para que todos los algoritmos laburen igual

	Result* R;
	list<Edge*> S;
	Edge *e = new Edge;
	origen --;
	destino --;
	if (destino<origen) swap(destino,origen);

	Graph *G = new Graph;
	Graph *M = new Graph;
	initGraph(G,nodesCant);
 	initGraph(M,nodesCant);
	int i =0;
	for (vector<Edge>::iterator it = aristas.begin() ; it != aristas.end(); ++it){

		e->id  = i;
		e->w1 = (*it).w1;
		e->w2 = (*it).w2;
		putEdge(G,(*it).u-1,(*it).v-1,e,1);
		i++;
	}

	//FIN estanadarizado

	//Uso Dijkstra para obtener una solucion.
	R = CalcularCaminoDijkstra(G,M,&S,0,origen,K,origen,destino);
/*
  	//uso Busqueda Local para obtener otra solucion
  if (R != NULL){

    busquedaLocal(R,G,nodesCant, origen, destino, K);

    printf("%d %d %d",R->w1,R->w2,R->k);
    for (list<int>::iterator it = R->C.begin() ; it != R->C.end(); ++it){
      printf(" %d",*it+1);
    }
    printf("\n");

  }*/
}
int main(int argc, char *argv[])
{
		    timeval tm1, tm2;
        string line;
        bool primerLinea = true;
        int n,m,u,v,K,v1,v2,w1,w2;  //los valores de entrada
        string sn,sm,su,sv,sK,sv1,sv2,sw1,sw2,nulo; //version string de la entrada
        int numLinea;// para evitar leer lineas de mas
        int id= 0;
        int pos;
        vector<Edge> aristas;
        //Comienzo la lectura del archivo
        while ( getline (cin,line) ){
              if(line[0]=='0') break;
              if(primerLinea){

                      tratarLinea(line,sn,sm,su,sv,sK,5);
                      n = atoi(sn.c_str());
                      m = atoi(sm.c_str());
                      u = atoi(su.c_str());
                      v = atoi(sv.c_str());
                      K = atoi(sK.c_str());
                      aristas.resize(m);
                      pos = 0;
                      numLinea = 0;
                      //SOLO DEBUG //cout << sn + " " + sm <<  " " + su << " " + sv << " " + sK << endl;
                      primerLinea=false;
                      continue;
              }

              tratarLinea(line,sw1,sw2,sv1,sv2,nulo,4);
      				v1 = atoi(sv1.c_str());
      				v2 = atoi(sv2.c_str());
      				w1 = atoi(sw1.c_str());
      				w2 = atoi(sw2.c_str());
    				//SOLO DEBUG //cout << sv1 + " " + sv2 <<  " " + sw1 << " " + sw2 << endl;
              Edge e = {id,v1,v2,w1,w2};
              aristas[pos] = e;
              pos++;
              numLinea++;
              if(numLinea == m){
    					//Result res = resolver(aristas,n,m,u,v,K);
              gettimeofday(&tm1, NULL);
              resolver(aristas,n,m,u,v,K);
              gettimeofday(&tm2, NULL);
              unsigned long long t = 1000 * (tm2.tv_sec - tm1.tv_sec) + (tm2.tv_usec - tm1.tv_usec) / 1000;
              printf("%ld %lld %s",n,t, "\n");
    					numLinea = 0;
    					primerLinea = true;
				}
		}

    return 0;
}
